#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
//class Solution {
//public:
//    int Fibonacci(int n) {
//        if (n == 0) return 0;
//        if (n == 1 || n == 2) return 1;
//        int f1 = 1, f2 = 1, ret = 1;
//        for (int i = 0; i < n - 2; i++)
//        {
//            ret = f1 + f2;
//            f1 = f2;
//            f2 = ret;
//        }
//        return ret;
//    }
//};

class Solution {
public:
    void reverse(vector<int>& nums, int begin, int end)
    {
        while (begin < end)
        {
            int temp = nums[begin];
            nums[begin] = nums[end];
            nums[end] = temp;
            begin++;
            end--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        k %= len;
        reverse(nums, 0, len - 1);
        reverse(nums, len - k, len - 1);
        reverse(nums, 0, len - k - 1);
    }
};

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            int count = 0;
            for (auto e : nums)
            {
                if (e >= l && e <= mid) count++;
            }
            if (count > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};